package com.fang.algorithm.leecode;

import java.util.HashSet;
import java.util.Set;

/**
 * @author fanglingxiao
 * @version 1.0
 * @description 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
 * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案
 * <p>
 * 输入：nums = [1,2,0]
 * 输出：3
 * <p>
 * 输入：nums = [3,4,-1,1]
 * 输出：2
 * <p>
 * 输入：nums = [7,8,9,11,12]
 * 输出：1
 * @date 2022/5/11 1:09 下午
 **/
public class L41_FirstMissingPositive {
    public static void main(String[] args) {
        int[] nums = new int[]{1};
        int positive = firstMissingPositive(nums);
        System.out.println(positive);
    }

    private static int firstMissingPositive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (num < 0) {
                continue;
            }
            set.add(num);
        }
        int ans = 0;
        for (int i = 0; i < set.size() + 1; i++) {
            ans = i + 1;
            if (set.contains(ans)) {
                continue;
            }
            return ans;
        }
        return ans;
    }
}
